package leetcodev1.字符串;

import leetcodev1.链表.Solution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode131 {

    //1.递归遍历
    public List<List<String>> partition(String s) {
        List<List<String>> ret = new ArrayList<>();
        int length = s.length();
        dfs(s, 0, ret, new ArrayList<>(), length);
        return ret;
    }

    //回溯
    private void dfs(String s, int start, List<List<String>> ret, List<String> route, int length) {
        if (start == length) {
            ret.add(new ArrayList<>(route));
        }

        //i终点
        for (int i = start + 1; i <= length; i++) {
            String substring = s.substring(start, i);
            if (isPalindromic(substring)) {
                //前进1步
                route.add(substring);
                dfs(s, i, ret, route, length);
                //回溯1步
                route.remove(route.size() - 1);
            }
        }
    }

    private boolean isPalindromic(String s) {
        //这里可加一个hashmap 只能提升查找效率
        //动态规划节约了切分+查找效率 还是蛮有意义的
        int length = s.length(), left = 0, right = length - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

}

class Answer131 {
    boolean[][] f;//动态规划
    List<List<String>> ret = new ArrayList<List<String>>();//结果
    List<String> ans = new ArrayList<String>();//中间过程
    int n;//n个数

    public List<List<String>> partition(String s) {
        n = s.length();
        f = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(f[i], true);//所有初始化成true
        }

        //遍历对角线上的所有元素
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1];//结合当前元素+内部元素结果
            }
        }

        dfs(s, 0);
        return ret;
    }

    public void dfs(String s, int i) {
        if (i == n) {
            ret.add(new ArrayList<String>(ans));
            return;
        }

        //i是起点 j是终点
        for (int j = i; j < n; ++j) {
            //当前是回文串则继续向下
            //利用空间换时间 避免每次都判断相同元素
            if (f[i][j]) {
                ans.add(s.substring(i, j + 1));
                dfs(s, j + 1);
                ans.remove(ans.size() - 1);
            }
        }
    }
}
